<?php

// Try to write a Boyer-Moore-Horspool string matching algorithm
// Match from end of pattern. If no match shift pattern right according to the shift table

// One of the most practical approach

$string = 'abbbbana';
$pattern = "bana";

$match = stringMatch($string, $pattern);
echo "$pattern matches $string at $match";

function stringMatch( $string, $pattern ){
	$m = strlen( $pattern );
	$n = strlen( $string );

	if( 0 == $m || 0 == $n ){
		return -1;
	}
	if( $n < $m ){
		return -1;
	}

	// Jump table
	$shift = array();
	for( $k=0; $k<$m-1; $k++ ){
		// If a same letter appear later in the string, the shift will be overwriten
		$shift[$pattern[$k]] = $m - $k - 1;
	}

	var_dump( $shift );

	$i = 0;
	// Every position
	while( $i <= ($n-$m) ){

		$j = $m - 1;
		while( $pattern[$j] == $string[ $i + $j ] ){
			$j--;
			if( $j < 0 ){
				return $i;
			}
		}

		// No match, shift
		if( isset($shift[$string[$i+$m-1]] ) ){
			$i += $shift[$string[$i+$m-1]];
		}
		else {
			$i += $m;
		}
	}

	return -1;
}